package site.wanjiahao.sort.uncompare;

import site.wanjiahao.sort.Sort;

// 使用桶排序
public class RadixSort2 extends Sort<Integer> {


    @Override
    protected void sort() {
        int max = array[0];
        for (int e: array) {
            if (e > max) {
                max = e;
            }
        }
        // 创建一个二维数组，存放元素
        int[][] buckets = new int[10][array.length];
        for (int divider = 1; divider <= max; divider*=10 ) {
            // 分别对每一位进行排序
            for (int i = 0; i < array.length; i++) {
                int num = array[i] / divider % 10;
                for (int j = 0; j < array.length; j++) {
                    // 找到桶最后一个元素存放
                    if (buckets[num][j] == 0) {
                        buckets[num][j] = array[i];
                        break;
                    }
                }
            }

            // 按顺序，存入原来的数组
            int n = 0;
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < array.length; k++) {
                    if (buckets[j][k] != 0) {
                        // 存在元素
                        array[n++] = buckets[j][k];
                        buckets[j][k] = 0;
                    }
                }
            }
        }
    }

}
